package a08_回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <p>
 * a10_复原IP地址复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/1/3
 */
public class a10_复原IP地址复习1 {

    public static void main(String[] args) {
        a10_复原IP地址复习1 test = new a10_复原IP地址复习1();
        List<String> list = test.restoreIpAddresses("0279245587303");
        System.out.println(list);
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        LinkedList<String> path = new LinkedList<>();
        char[] chars = s.toCharArray();
        traversal(result, path, chars, 0);
        return result;
    }

    private void traversal(List<String> result,
                           LinkedList<String> path,
                           char[] chars,
                           int startIdx){
        if(path.size() == 3){
            if (isValid(chars, startIdx, chars.length - 1)) {
                path.add(splitArray(chars, startIdx, chars.length - 1));
                result.add(path.stream().collect(Collectors.joining(".")));
                path.removeLast();
                return;
            }else {
                return;
            }
        }

        for (int i = startIdx; i <= Math.min(chars.length - 1, startIdx + 3); i++) {
            if (!isValid(chars, startIdx, i)) {
                continue;
            }
            path.add(splitArray(chars, startIdx, i));
            traversal(result, path, chars, i + 1);
            path.removeLast();
        }
    }

    private String splitArray(char[] chars,int leftIdx,int rightIdx){
        StringBuilder sb = new StringBuilder();
        while (leftIdx <= rightIdx) {
            sb.append(chars[leftIdx]);
            leftIdx++;
        }
        return sb.toString();
    }

    private boolean isValid(char[] chars,int leftIdx,int rightIdx){
        if (leftIdx > rightIdx) {
            return false;
        }

        if(chars[leftIdx] == '0' && leftIdx != rightIdx){
            return false;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = leftIdx; i <= rightIdx; i++) {
            if(chars[i] < '0' || chars[i] > '9'){
                return false;
            }else {
                sb.append(chars[i]);
            }
        }

        if(Long.valueOf(sb.toString()) > 255){
            return false;
        }

        return true;
    }
}
